Sufficiency theorems for target capture

A dynamical system is assumed to be governed by a set of ordinary differential equations subject to control. The set of points in state space from which there exist permissible controls that can transfer these points to a prescribed target set in a finite time interval is called a capture set. The task of determining the capture set is studied in two contexts. first, in the case of the system subject to a single control vector; and second, in the case of the system subject to two control vectors each operated independently. In the latter case, it is assumed that one controller's aim is to cause the system to attain the target, and the other's is to prevent that from occurring.Sufficient conditions are developed that, when satisfied everywhere on the interior of some subset of the state space, ensure that this subset is truly a capture set. A candidate capture set is assumed to have already been predetermined by independent methods. The sufficient conditions developed herein require the use of an auxiliary scalar function of the state, similar to a Lyapunov function.To ensure capture, five conditions must be satisfied. Four of these constrain the auxiliary state function. Basically, these four conditions require that the boundary of the controllable set be an envelope of the auxiliary state function and that that function be positive inside the capture set, approaching zero value as the target set is approached. The final condition tests the inner product of the gradient of the auxiliary state function with the system state velocity vector. If the sign of that inner product can be made negative everywhere within the test subset, then that subset is a capture set.Dedicated to Professor A. BusemannThe authors are indebted to Professors G. Leitmann and J. M. Skowronskii for their useful comments and discussion.     

Stackelberg strategies in linear-quadratic stochastic differential games

This paper obtains the Stackelberg solution to a class of two-player stochastic differential games described by linear state dynamics and quadratic objective functionals. The information structure of the problem is such that the players make independent noisy measurements of the initial state and are permitted to utilize only this information in constructing their controls. Furthermore, by the very nature of the Stackelberg solution concept, one of the players is assumed to know, in advance, the strategy of the other player (the leader). For this class of problems, we first establish existence and uniqueness of the Stackelberg solution and then relate the derivation of the leader's Stackelberg solution to the optimal solution of a nonstandard stochastic control problem. This stochastic control problem is solved in a more general context, and its solution is utilized in constructing the Stackelberg strategy of the leader. For the special case Gaussian statistics, it is shown that this optimal strategy is affine in observation of the leader. The paper also discusses numerical aspects of the Stackelberg solution under general statistics and develops algorithms which converge to the unique Stackelberg solution.This work was performed while the second author was on sabbatical leave at the Department of Applied Mathematics, Twente University of Technology, Enschede, Holland.     

Combat games

We propose a mathematical formulation of a combat game between two opponents with offensive capabilities and offensive objectives. Resolution of the combat involves solving two differential games with state constraints. Depending on the game dynamics and parameters, the combat can terminate in one of four ways: (i) the first player wins, (ii) the second player wins, (iii) a draw (neither wins), or (iv) joint capture. In the first two cases, the optimal strategies of the two players are determined from suitable zero-sum games, whereas in the latter two the relevant games are nonzero-sum. Further, to avoid certain technical difficulties, the concept of a -combat game is introduced.Dedicated to G. LeitmannThe first author wishes to acknowledge the friendship and guidance of George Leitmann, beginning in the author's student days at Berkeley and continuing to the present time. All the authors thank George Leitmann for many recent fruitful discussions on differential games.on sabbatical leave from Technion, Israel Institute of Technology, Haifa, Israel.     

A game locating a needle in a square haystack

The following hider-seeker zero-sum game is considered. The hider hides a needle of length , in the closed unit square, and the seeker tries to locate it by shooting in a straight line across the square. The payoff to the seeker is 1 if he hits the needle and 0 otherwise.A solution of the game is obtained when or whena lies in either of the intervals and ; in addition, it is shown that, whenn is a positive integer anda=1/n, the value of the game is 1/2n. The properties of the solutions are in marked contrast to those for the analogous game over the closed unit disc, which the authors solved in a previous paper, and suggest that a complete solution may well be difficult. It is also shown that every member of a whole class of haystack games has a value.     

A pursuit-evasion differential game with noisy measurements of the evader's bearing from the pursuer

A stochastic pursuit-evasion differential game involving two players, E and P, moving in the plane is considered. It is assumed that player E (the evader) has complete observation of the position and velocity of player P, whereas player P (the pursuer) can measure the distanced (P, E) between P and E but receives noise-corrupted measurements of the bearing of E from P. Three cases are dealt with: (a) using the noise-corrupted measurements of , player P applies the proportional navigation guidance law; (b) P has complete observation ofd (P, E) and (this case is treated for the sake of completeness); (c) using the noise-corrupted measurements of , P applies an erroneous line-of sight guidance law. For each of the cases, sufficient conditions on optimal strategies are derived. In each of the cases, these conditions require the solution of a nonlinear partial differential equation on a in ². Finally, optimal strategies are computed by solving the corresponding equations numerically.     

On linear-quadratic Gaussian continuous-time Nash games

Two classes of linear-quadratic Gaussian continuous-time Nash games are considered. Their main characteristic is that the -fields with respect to which the control actions of the players have to be measurable at each instance of time are not affected by the past controls of the players. We show that, if a solution exists, then there exists a solution linear in the information, and also show how to construct all the solutions. Several conditions guaranteeing the existence of a unique solution are also given.This work was supported in part by the United States Air Force, Office of Scientific Research, under Grants Nos. AFOSR-80-0171 and AFOSR-82-0174.     

Infinitely constrained optimization problems

A generalized cutting-plane algorithm designed to solve problems of the form min{f(x) :x X andg(x,y) 0 for ally Y} is described. Convergence is established in the general case (f,g continuous,X andY compact). Constraint dropping is allowed in a special case [f,g(·,y) convex functions,X a convex set]. Applications are made to a variety of max-min problems. Computational considerations are discussed.Dr. Falk's research was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under AFOSR Contract No. 73–2504.     

Sufficient conditions for preference optimality

Preference optimality is an optimality concept in multicriteria problems, that is, in problems where several criteria are to beoptimized simultaneously. Formally, one wishes to optimizeN criteriag _i(·) or, equivalently, a criterion vectorg(·) ^N , subject to either functional constraints in programming or to side conditions which are differential equations in optimal control. Subject to these constraints, one obtains forg(·) a set of attainable values in ^N . This set is preordered by the introduction of a complete preordering ; a controlu*(·) or a decisionx*, then, is preference-optimal if it results ing(u*(·))g(u(·)) for all admissible controlsu(·) or ifg(x*)g(x) for all feasible decisionsx. The present paper concerns sufficient conditions for preference-optimal control and for preference-optimal decisions.     

Zero-sum Markov games and worst-case optimal control of queueing systems

Zero-sum stochastic games model situations where two persons, called players, control some dynamic system, and both have opposite objectives. One player wishes typically to minimize a cost which has to be paid to the other player. Such a game may also be used to model problems with a single controller who has only partial information on the system: the dynamic of the system may depend on some parameter that is unknown to the controller, and may vary in time in an unpredictable way. A worst-case criterion may be considered, where the unknown parameter is assumed to be chosen by nature (called player 1), and the objective of the controller (player 2) is then to design a policy that guarantees the best performance under worst-case behaviour of nature. The purpose of this paper is to present a survey of stochastic games in queues, where both tools and applications are considered. The first part is devoted to the tools. We present some existing tools for solving finite horizon and infinite horizon discounted Markov games with unbounded cost, and develop new ones that are typically applicable in queueing problems. We then present some new tools and theory of expected average cost stochastic games with unbounded cost. In the second part of the paper we present a survey on existing results on worst-case control of queues, and illustrate the structural properties of best policies of the controller, worst-case policies of nature, and of the value function. Using the theory developed in the first part of the paper, we extend some of the above results, which were known to hold for finite horizon costs or for the discounted cost, to the expected average cost.     

Computation of Nash equilibria: admissibility of parallel gradient descent

This paper offers some analytical results on the practical computation of Nash equilibria, which has been demonstrated to be relevant in real-world applications. In particular, the parallel gradient descent is analyzed from this perspective, and admissibility conditions are presented. First, the parallel gradient descent is defined in terms of update strategies and iteration times. It is shown that convergence is related to the contraction property. The analysis then derives sufficient conditions for the update strategies and the iteration times that ensure convergence. An illustrative example is presented in order to demonstrate practical implementation aspects and motivate the practical use of game theory in a wide spectrum of applications varying from economics to intelligent sensor systems.The author thanks T. Basar, H. P. Benson, and an anonymous reviewer for numerous helpful comments on the paper.